P5427 [USACO19OPEN]Left Out

为了书写方便,我们将L'L'表示为0,R'R'表示为1。

现在题目转化为给你一个01矩阵,每次可将一行或一列的01反转,要求最后只有一个1或只有一个0,问能否办到。

现在,我们将第一行和第一列的元素全变为1(0也可以),这个很好办到,翻转第一行的元素就将该元素所在列翻转,列同理。

经过以上操作之后,我们会得到这样一个矩阵:

1.PNG

我们可以将答案分为三部分讨论,即红色部分,紫色部分,黄色部分。

1.如果答案在红色区域,为了使它和第1行,第1列不同,我们需要将第1行,第1列各翻一次,得到这样一个矩阵:

2.PNG

那么显然,黄色部分必须全为1。


2.如果答案在黄色区域,那么黄色区域只能有且仅有1个1。这时整个图也只有1个1。

3.如果答案在紫色区域,那么黄色区域只能有且仅有1行或1列1,这样就可以交换一次得到。

4.如果上述三种情况不满足,输出-1。

注意2,3要求仅有,可以用tot记录判断或者用标记。

程序中的check1,2,3check1,2,3分别对应情况1,2,3。

标程:

#include <cstdio>

const int MAXN = 1000;
int n, x , y;
bool state[ MAXN + 5 ][ MAXN + 5 ];

void operation( int x , bool f ) {	//将一行或一列取反
	if( f )
		for( int i = 1 ; i <= n ; i ++ )
			state[ x ][ i ] = !state[ x ][ i ];
	else
		for( int i = 1 ; i <= n ; i ++ )
			state[ i ][ x ] = !state[ i ][ x ];
}
void update( int xx , int yy ) {	//更新答案
	if( xx < x || ( xx == x && yy < y ) )
		x = xx , y = yy;
}
bool check1( ) {
	for( int i = 2 ; i <= n ; i ++ )
		for( int j = 2 ; j <= n ; j ++ )
			if( state[ i ][ j ] == 0 ) return 0;
	return 1;
}
bool check2( ) {
	x = 1005 , y = 1005;
	bool f = 1;
	for( int i = 2 ; i <= n ; i ++ )
		for( int j = 2 ; j <= n ; j ++ )
			if( state[ i ][ j ] == 1 ) {
				if( f )
					f = 0 , x = i , y = j;
				else
					return 0;
			}
	return !f;
}
bool check3( ) {
	x = 1005 , y = 1005;
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 2 ; j <= n ; j ++ ) {
			if( !state[ i ][ j ] ) break;
			if( j == n ) 
				update( i , 1 );
		}
	for( int j = 1 ; j <= n ; j ++ )
		for( int i = 2 ; i <= n ; i ++ ) {
			if( !state[ i ][ j ] ) break;
			if( i == n ) 
				update( 1 , j );
		}
	return ( x == 1005 || y == 1005 ) ? 0 : 1; 
}

int main( ) {
	//freopen("transitioning.in","r",stdin);
	//freopen("transitioning.out","w",stdout);
	
	scanf("%d",&n);
	char c;
	for( int i = 1 ; i <= n ; i ++ ) {
		getchar( );
		for( int j = 1 ; j <= n ; j ++ )
			scanf("%c",&c) , state[ i ][ j ] = c == 'L' ? 0 : 1;
	}
	for( int i = 1 ; i <= n ; i ++ )
		if( state[ i ][ 1 ] ) operation( i , 1 );
	for( int i = 1 ; i <= n ; i ++ )
		if( state[ 1 ][ i ] ) operation( i , 0 );
	
	if( check1( ) ) printf("1 1\n");
	else if( check2( ) ) printf("%d %d\n",x,y);
	else if( check3( ) ) printf("%d %d\n",x,y); 
	else printf("-1\n");
	return 0;
}